Round Overview
Discuss this match
Since constraints are quite small, you can iterate over all possible lengths for each stick. For three positive integers i, j, k it’s impossible to build a triangle with such sides in only one case - if the biggest of three numbers is equal to or greater than the sum of the other two. For example, if i is the biggest one (ties allowed) then a triangle can be built if and only if i < j + k
You should iterate over all possible triples (i, j, k) and find the biggest value of i + j + k for triples allowing to build a triangle. Note that i < j + k can be written as 2 \cdot i < i + j + k, what allows to simplify implementing a bit. You don’t need to check which of i, j, k is the biggest - just check if 2 \cdot MAX < i + j + k.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
// brute force solution, complexity O(a*b*c)
// because of small constraints, this code gets AC
public: int maxPerimeter(int a, int b, int c) {
int best = -1;
for (int i = 1; i <= a; ++i)
for (int j = 1; j <= b; ++j)
for (int k = 1; k <= c; ++k)
if (max({
i,
j,
k
}) * 2 < i + j + k)
best = max(best, i + j + k);
return best;
}
There is a faster approach though. Instead of iterating with i, j, k, we can make some simple observations.
First, what if the given three integers a, b, c already allow to build a triangle? Then we shouldn’t shorten any stick - just return a + b + c because it’s the biggest possible perimeter.
And if a, b, c don’t allow to build a triangle, one of these three numbers is apparently too big and we have to decrease it. Let’s say that a is the biggest one (so a \ge b + c). We must decrease a to b + c - 1 or some smaller value, to satisfy an inequality a < b + c. It turns out that we don’t have to decrease anything more! For any positive values of b, c we can build a triangle with sides b + c - 1, b, c (note that b + c - 1 < b + c). Since we want to maximize the perimeter, it’s optimal not to decrease anything more. We return (b + c - 1) + b + c = 2 \cdot (b + c) - 1 (in a case with a being the biggest of three given numbers).
1
2
3
4
5
6
7
// smarter O(1) solution
public: int maxPerimeter(int a, int b, int c) {
if (b > a) swap(a, b);
if (c > a) swap(a, c); // after that, a is the biggest one
if (a < b + c) return a + b + c; // we can build a triangle with sides a, b, c
return 2 * (b + c) - 1; // we must decrease the biggest number, as explained in the editorial
}
DivisibleSetDiv2
Problem Details
The solution is very simple to implement but not so trivial to prove. It turns out that the answer is “Possible” if and only if sum_{i=0}^{n-1} \frac{1}{b_i} \le 1. You can find a detailed proof below.
We are asked if there exists a sequence of powers of two (a_0, a_1, \ldots, a_{n-1}) that for every i:
a_i \ge 2
a_i^{b_i} is divisible by \prod_{j=0}^{n-1} a_j.
Let x_i denote an exponent in a_i (i.e. 2^{x_i} = a_i). We can now simplify the second condition:
a_i^{b_i} = 2^{b_i \cdot x_i} is divisible by \prod_{j=0}^{n-1} a_j = 2^S where S = \sum_{j=0}^{n-1} x_j
b_i \cdot x_i \ge \sum_{j=0}^{n-1} x_j = S
x_i \ge \frac{S}{b_i} (this condition is EQUIVALENT to the initial divisibility condition)
Recall that 2 \le a_i = 2^{x_i}, what gives us x_i \ge 1. So, we are looking for a sequence of positive integers (x_0, x_1, \ldots, x_{n-1}) such that x_i \ge \frac{S}{b_i} for every i.
We can sum up n inequalities of form x_i \ge \frac{S}{b_i} to get:
x_0 + x_1 + \ldots + x_{n-1} \ge \frac{S}{b_0} + \frac{S}{b_1} + \ldots + \frac{S}{b_{n-1}}
S \ge \frac{S}{b_0} + \frac{S}{b_1} + \ldots + \frac{S}{b_{n-1}}
1 \ge \frac{1}{b_0} + \frac{1}{b_1} + \ldots + \frac{1}{b_{n-1}} (*)
We showed that the last inequality must hold true (though we didn’t show that it’s equivalent to the initial conditions). If it isn’t true then we can return “Impossible”. It turns out that otherwise we can choose values x_i to satisfy all x_i \ge \frac{S}{b_i} (see the next paragraph). Hence, we can return “Possible”.
For any positive real constant C consider assuming x_i = \frac{C}{b_i}. From the inequality (*) we have C \ge \frac{C}{b_0} + \frac{C}{b_1} + \ldots + \frac{C}{b_{n-1}}. Note the the right side here is equal to x_0 + x_1 + \ldots + x_{n-1} = S, so we get C \ge S. It means that x_i = \frac{C}{b_i} \ge \frac{S}{b_i} what is equivalent to the initial divisibility conditions, as we showed before. The last thing is that all x_i should be integers - to ensure that we can choose C = LCM(1, 2, \ldots, 10) (least common multiple). So, if there exists any solution, one solution would be to just take x_i = \frac{2520}{b_i}.
1
2
3
4
5
6
7
8
9
public String isPossible(int b[]) {
double sum = 0.0;
for (int bi: b)
sum += 1.0 / bi;
if (sum <= 1.0 + 1e-7) // that 1e-7 is necessary because maybe the sum is equal to 1 it is stored as e.g. 1.0000000000000001 in the memory
return "Possible";
else
return "Impossible";
}
1
2
3
4
5
6
public string isPossible(vector < int > b) {
int LCM = 2520, sum = 0;
for (int bi: b)
sum += LCM / bi; // sum up 1/b multiplied by LCM to avoid floats
return (sum <= LCM) ? "Possible" : "Impossible";
}
There is an O(n^2) solution with building a trie and running top-down dynamic programming on it (you can see the code below), but you should try to solve the Div1 version of this problem, with n \le 200,000. It may encourage you that the code there is much shorter. You can find the editorial for that version here: XorOrderDiv1.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
// O(n^2)
#include <bits/stdc++.h>
using namespace std;
struct nodes {
nodes * L, * R;
int size;
int id;
nodes() {
L = R = NULL;
size = 1;
id = -1;
}
void calcSize() {
size = 0;
if (L != NULL)
size += L - > size;
if (R != NULL)
size += R - > size;
if (size == 0)
size++;
}
}* root;
long long ans[1001];
int n, M;
void addNode(int val, int id, nodes * cur, int curPos) {
if (curPos < 0) {
cur - > id = id;
cur - > calcSize();
return;
}
if ((val & (1 << curPos)) == 0) {
if (cur - > L == NULL)
cur - > L = new nodes();
addNode(val, id, cur - > L, curPos - 1);
} else {
if (cur - > R == NULL)
cur - > R = new nodes();
addNode(val, id, cur - > R, curPos - 1);
}
cur - > calcSize();
}
void solve(nodes * cur, vector < long long > lis) {
if (cur - > L == NULL && cur - > R == NULL) {
long long sum = 0;
for (int i = 0; i < n; i++)
sum += lis[i];
for (int i = 0; i < n; i++)
ans[cur - > id] += 1 LL * i * i * lis[i] * ((1 LL << M) / sum);
} else if (cur - > L == NULL) {
solve(cur - > R, lis);
} else if (cur - > R == NULL) {
solve(cur - > L, lis);
} else {
{
vector < long long > nextLis(n);
for (int i = 0; i < n; i++) {
nextLis[i] += lis[i];
if (i + cur - > R - > size < n)
nextLis[i + cur - > R - > size] += lis[i];
}
solve(cur - > L, nextLis);
} {
vector < long long > nextLis(n);
for (int i = 0; i < n; i++) {
nextLis[i] += lis[i];
if (i + cur - > L - > size < n)
nextLis[i + cur - > L - > size] += lis[i];
}
solve(cur - > R, nextLis);
}
}
}
class XorOrderDiv2 {
public: vector < long long > getExpectation(int m, vector < int > a) {
n = a.size();
M = m;
root = new nodes();
for (int i = 0; i < a.size(); i++)
addNode(a[i], i, root, M - 1);
memset(ans, 0, sizeof(ans));
vector < long long > lis(n);
lis[0] = 1;
solve(root, lis);
vector < long long > ret;
for (int i = 0; i < n; i++) {
//cout << ans[i] << " " ;
ret.push_back(ans[i]);
}
//cout << endl;
return ret;
}
};
DivisibleSetDiv1
Problem Details
Participants in Division 2 were given an easier version of this problem (link to the statement). The differences are:
In Div2 elements of a new sequence (a_i) can only be powers of two.
In Div2 elements of a new sequence (a_i) don’t have to be distinct.
In Div2 every a_i^{b_i} must be divisible by the product of all a_j (including a_i itself).
These two problems are more similar than they seem to be. You should first try to solve the easier version (you can also check out its editorial).
Ok, let’s deal with the harder version. Since a_i \ge 2, there must be at least one prime dividing some a_i. The divisibility condition implies that then all a_0, \ldots, a_{n-1} must be divisible by that prime. For a moment let’s not care about “numbers should be distinct” and then we can consider every prime independently. So let’s choose any prime to get a problem similar to the Div2 version.
In the easier version we had b_i \cdot x_i \ge \sum_{j=0}^{n-1} x_j = S. In this problem it is b_i \cdot x_i \ge \sum_{j \ne i} x_j = S - x_i from which we get:
(b_i + 1) \cdot x_i \ge S
x_i \ge \frac{S}{b_i + 1} (yeah, it’s almost the same we got in the Div2 version)
I) If sum_i \frac{1}{b_i+1} > 1 -> return “Impossible”, similarly to the Div2 version.
II) If b_i are distinct and sum_i \frac{1}{b_i+1} \le 1 -> return “Possible”. We can take x_i = \frac{LCM}{b_i} and for distinct b_i we would get distinct x_i (and thus distinct a_i).
III) Not distinct b_i and 1 = \sum_i \frac{1}{b_i} -> return “Impossible”. Editorial for Div2 showed that x_i \ge \frac{S}{b_i} implies 1 \ge \sum_i \frac{1}{b_i}. If there is a strict “greater than” x_i > \frac{S}{b_i} for at least one i, we get a strict inequality 1 > \sum_i \frac{1}{b_i}. So, if 1 = \sum_i \frac{1}{b_i} then there must be x_i = \frac{S}{b_i} for all i. If some b_i are equal, also some x_i will be equal. Since x_i are equal for any chosen prime to consider, also respective a_i must be equal.
IV) Not distinct b_i and 1 > \sum_i \frac{1}{b_i} (**) -> return “Possible”. Let’s choose some extremely big C divisible by all b_i, and then set x_i = \frac{C}{b_i}. From the assumed inequality (**) we have C > \sum_i \frac{C}{b_i} = S so also x_i = \frac{C}{b_i} > \frac{S}{b_i} (we proved a strict inequality). Let’s slightly change numbers x_i to make them distinct (e.g. 60, 60, 95, 95, 95 to 60, 61, 94, 95, 96). By choosing big enough C, we can get arbitrarily small relative changes of x_i and S . In particular, for small enough relative changes the inequalities x_i > \frac{S}{b_i} will still hold true.
1
2
3
4
5
6
7
8
9
10
11
public String isPossible(int b[]) {
double sum = 0.0;
for (int bi: b)
sum += 1.0 / (bi + 1);
final double EPS = 1e-9;
Arrays.sort(b);
for (int i = 0; i < b.length - 1; i++)
if (b[i] == b[i + 1] && abs(1 - sum) < EPS)
return "Impossible";
return (sum < 1 + EPS) ? "Possible" : "Impossible";
}
1
2
3
4
5
6
7
8
9
10
11
public string isPossible(vector < int > b) {
bool areDifferent = true;
for (int i = 0; i < (int) b.size(); ++i)
for (int j = i + 1; j < (int) b.size(); ++j)
if (b[i] == b[j])
areDifferent = false;
int LCM = 5 * 7 * 8 * 9 * 11, sum = 0;
for (int bi: b)
sum += LCM / (bi + 1); // sum up 1/(b+1) multiplied by LCM to avoid floats
return (sum < LCM || (sum == LCM && areDifferent)) ? "Possible" : "Impossible";
}
Let’s try to find s_0 - the sum of squares of places of the 0-th person (let’s call him Bob). The standard trick in problems with the sum of squares of places is that we can instead iterate over (n-1)^2 pairs of other n-1 participants (a pair doesn’t necessarily contain two distinct participants) and for each such pair add to the answer the number of times all participants in this pair are better than Bob. Here, “all” means “both” if a pair contains two distinct participants and it means “the only” if a pair contains one participant only.
For each of other n-1 participants the only important thing is when he/she wins with Bob. It turns out that “does he/she win with Bob” is always decided by the first bit where a_0 and a_i differ. For example, for a_0 = 101\mathbf{0}1010_{(2)} and a_i = 101\mathbf{1}1111_{(2)} Bob wins exactly in days where the fourth bit is 0. So, other n-1 participants can be divided into m groups, according to the first bit different from a bit in a_0. For example, for m = 4 and a_0 = 1111_{(2)} we would get groups (classes):
1110 (participants with number a_i where first three bits are 1’s and the last one is 0)
110? (the last bit is either 0 or 1)
10??
0???
So, there are m groups, numbered 0 through m-1. Let’s say that the i-th group contains c_i participants. Instead of iterating over pairs of participants, it’s enough to iterate over pairs of groups. A pair of two distinct groups r, t represents c_r \cdot c_t pairs of participants. For each such pair of participants we want to know the number of days in which Bob loses with them both. In a day number two distinct bits must be set to some particular value (one bit because of each group), so there are 2^{m-2} such days. So we add c_r \cdot c_t \cdot 2^{m-2} to the answer.
There are also pairs of form (r, r) (where one group is listed two times). It represents (c_r)^2 pairs of participants and for each such pair only one bit in the day number if fixed. So, there are 2^{m-1} days in which Bob loses with this group.
For each fixed person (Bob) we need to divide other n-1 participants into m groups and find sizes c_0, c_1, \ldots, c_{m-1}. We can achieve it in O(n \cdot m) in total by building a trie once. Every vertex should store participants with a_i starting with some particular prefix (we care about binary forms of course). The root should contain all n participants. Participants should be divided into two children of the root, according to the first bit (and so on). For the given constraints you could use O(n \cdot m) memory but it can’t be O(2^m). The needed sizes c_0, c_1, \ldots, c_{m-1} can be found on the path from the fixed a_i (leaf) to the root. More precisely: every group is a vertex that isn’t on the path but its parent is on the path.
What is written above is enough for O(n \cdot m^2) solution, what should get AC. We can make it even faster though. Since \sum c_i = n - 1, we can write:
(n - 1)^2 = \sum (c_i)^2 + 2 \sum_{r \ne t} (c_r \cdot c_t)
It’s enough to find \sum (c_i)^2 and then we will also know \sum_{r \ne t} (c_r \cdot c_t). Knowing these two sums, it’s easy to obtain the answer (you should multiply each of them by something like 2^{m-2} or similar, and add them). So, for each Bob we need the sum of squares of sizes of groups. In this problem it’s good to think a bit before coding. In the code below you can see a recursive approach that finds those “sums of squares of sizes” in one run. Starting from the root, for each child x it adds to ans[x] the squared size of the other child, and then runs recursively.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
// O(nm) time and O(n) memory
const int mod = 1e9 + 7;
struct XorOrderDiv1 {
void rec(int k, vector < int > & indices,
const vector < int > & in, vector < int > & ans) {
if (indices.size() <= 1) return;
vector < int > a, b;
for (int i: indices) {
if (in [i] & (1 << k)) a.push_back(i);
else b.push_back(i);
}
vector < int > ()
.swap(indices);
for (int x: a) ans[x] = (ans[x] + (long long) b.size() * b.size()) % mod;
for (int x: b) ans[x] = (ans[x] + (long long) a.size() * a.size()) % mod;
rec(k - 1, a, in, ans);
rec(k - 1, b, in, ans);
}
public: int get(int m, int n, int a0, int b) {
vector < int > in(n, a0);
for (int i = 1; i < n; ++i)
in [i] = (in [i - 1] + (long long) b) % (1 << m);
vector < int > ans(n, 0);
vector < int > indices;
for (int i = 0; i < n; ++i)
indices.push_back(i);
rec(30, indices, in, ans);
int ret = 0;
for (int & x: ans) {
x = (x + (long long)(n - 1) * (n - 1)) % mod;
for (int i = 0; i < m - 2; ++i)
x = 2 * x % mod;
if (m == 1) {
assert(x % 2 == 0);
x /= 2;
}
ret ^= x;
}
return ret;
}
};
ConnectedStates
Problem Details
Let A, B, \ldots, Z denote the input numbers (numbers of cities in each state) and let a, b, \ldots, z denote the respective degrees (called x[i] in the statement). From Prufer Sequences we know that the number of trees with fixed degrees a,b,\ldots,z is \frac{(n-2)!}{(a-1)! \cdot (b-1)! \cdot \ldots \cdot (z-1)!}. Also, for each state we must connect incident edges to some particular cities - there are A^a \cdot B^b \cdot \ldots ways for that. Finally, the statement says to sum up (a \cdot b \cdot \ldots) over all possibilities. So, we are asked to find:
`
\sum_{a + b + \ldots + z = 2 \cdot n - 2} \frac{(n-2)!}{(a-1)! \cdot (b-1)! \cdot \ldots} \cdot (A^a \cdot B^b \cdot \ldots) \cdot (a \cdot b \cdot \ldots) \\ = (n - 2)! \cdot \sum_{a + b + \ldots + z = n - 2} \frac{A^{a+1} \cdot B^{b+1} \cdot \ldots}{a! \cdot b! \cdot \ldots} \cdot ((a+1) \cdot (b+1) \cdot \ldots) \\ = (n - 2)! \cdot (A \cdot B \cdot \ldots) \cdot \sum_{a + b + \ldots + z = n - 2} \frac{A^a \cdot B^b \cdot \ldots}{a! \cdot b! \cdot \ldots} \cdot ((a+1) \cdot (b+1) \cdot \ldots)
`
Note that in the first sum above there is a, b, \ldots \ge 1 and then we decrease all a,b,\ldots by 1, so we only require a,b,\ldots \ge 0 later.
It isn’t hard to compute the above sum using standard dynamic programming in O(n^3) (i.e. we want to sum up products of \frac{A^a \cdot (a+1)}{a!} over all possible tuples (a, b, \ldots, z)). To make it O(n^2), we will try to use a very simple formula: Multinomial theorem. (Also, one other solution is to use use generating functions.)
We can’t immediately use the Multinomial theorem because of a product (a+1)(b+1)\cdot \ldots (z+1). So let’s multiply these brackets to get (1 + a + b + \ldots + z + ab + ac + \ldots + abdf + \ldots). Let’s take one component (let it be abd) and let’s multiply it by the rest of the derived formula for the sum:
`
\sum_{a + b + \ldots + z = n - 2} \frac{A^a \cdot B^b \cdot \ldots}{a! \cdot b! \cdot \ldots} \cdot abd \\ = \sum_{a + b + \ldots + z = n - 2} \frac{A^a \cdot B^b \cdot C^c \ldots}{(a-1)! \cdot (b-1)! \cdot c! \cdot (d-1)! \cdot \ldots} \\ = A \cdot B \cdot D \cdot \sum_{a + b + \ldots + z = n - 2} \frac{A^{a-1} \cdot B^{b-1} \cdot C^c \cdot D^{d-1} \cdot \ldots}{(a-1)! \cdot (b-1)! \cdot c! \cdot (d-1)! \cdot \ldots} \\ = A \cdot B \cdot D \cdot \sum_{a + b + \ldots + z = n - 2 - k} \frac{A^a \cdot B^b \cdot C^c \cdot D^d \cdot \ldots}{a! \cdot b! \cdot \ldots \cdot z!} \\ = A \cdot B \cdot D \cdot (A + B + \ldots + Z)^{n - 2 - k} \cdot \frac{1}{(n-2-k)!}
`
Here, k is the number of numbers in a chosen component A \cdot B \cdot D, so k = 3 in this case.
We must iterate over k (the number of numbers in the component) and for each k find the sum of products of k distinct input numbers (e.g. for k = 2 we need A \cdot B + A \cdot C + \ldots + B \cdot C + \ldots). To the answer we must add this sum multiplied by \frac{(n-2)!}{(n-2-k)!} \cdot (A \cdot B \cdot \ldots \cdot Z) \cdot (A + B + \ldots + Z)^{n-2-k}.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
public class ConnectedStates {
public static final int mod = 1_000_000_007;
int add(int x, int y) {
x += y;
if (x >= mod)
x -= mod;
return x;
}
int mul(int x, int y) {
long p = (long) x * (long) y % mod;
return (int) p;
}
int binpow(int x, int to) {
int y = 1;
while (to > 0) {
if ((to & 1) == 1)
y = mul(x, y);
x = mul(x, x);
to >>= 1;
}
return y;
}
public int getSum(int a[]) {
int n = a.length;
int b[] = new int[n + 1];
b[0] = 1;
for (int x: a) {
for (int j = n; j > 0; --j)
b[j] = add(b[j], mul(x, b[j - 1]));
}
// b[k] is k-th symmetric polynomial, i.e. sum of products over all k-tuples
// e.g. b[2] = A*B + A*C + A*D + ... + B*C + B*D + ...
int s = b[1]; // sum of a[i]
int p = b[n]; // product of a[i]
int ans = 0;
int cur = 1;
for (int k = 0; k <= n - 2; ++k) {
int bon = 1;
bon = mul(bon, cur);
bon = mul(bon, binpow(s, n - 2 - k));
bon = mul(bon, b[k]);
bon = mul(bon, p);
ans = add(ans, bon);
cur = mul(cur, n - 2 - k);
}
return ans;
}
};